package offerbook.Code27_BST_Link_Array_Converse;

import utils.ListNode;
import utils.TreeNode;
import utils.TreeUtil;


/**
 * Created at 2019/10/22 0022 下午 3:00
 * 有序链表转BST，其实和有序数组转BST思路一致。就是找中点的问题。
 * 方式1：链表转数组
 * 方式2：找链表中点，快慢指针
 */
public class Code27_ConvertLinkToBST {

    //方式1：链表转数组
    public static TreeNode convertLinkToBST1(ListNode head){

        if(head == null){
            return null;
        }
        //如果list是双向链表，那么array可以改成ListNode，
        // 然后调用重建的时候只要进行重新连接，不用再new了
        int[] array = convertLinkToArray(head);
        return Code27_ConvertArrayToBST.reconstructBST(array);
    }
    //方式2：对链表进行二分
    public static TreeNode convertLinkToBST2(ListNode head){
        if(head == null)  return null;
        //链表只剩下一个节点
        if(head.next == null) return new TreeNode(head.val);

        //下面要考虑只有两个节点情况,只剩两个点的时候，slow = slowPre ，fast = slow.next
        //找中间点
        ListNode slow = head;
        ListNode fast = head;
        //记录中间的前一个点，置为左侧递归的左节点
        ListNode slowPre = head;
        while (fast.next != null && fast.next.next != null){
            slowPre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //右边起始点
        fast = slow.next;
        //把链表重置为一半: slow.pre.next = null ,从slow断开
        slowPre.next = null;
        //中间点
        TreeNode node = new TreeNode(slow.val);
        //只剩两个点的时候，slow = slowPre ，fast = slow.next。slow若再去递归左侧，会导致多出一个点
        if(slowPre != slow){
            node.left = convertLinkToBST2(head);
        }
        node.right = convertLinkToBST2(fast);
        return node;
    }
    private static int[] convertLinkToArray(ListNode head) {
        if(head == null){
            return null;
        }
        int length = 0;
        ListNode cur = head;
        while (head != null){
            length ++;
            head = head.next;
        }
        int [] res = new int[length];
        int index = 0;
        while (cur != null){
            res[index++] = cur.val;
            cur = cur.next;
        }
        return res;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5, 7, 8, 10};
        int[] arr1 = {-10, -3, 0, 5, 9};
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(4);
        head1.next.next.next = new ListNode(5);
        head1.next.next.next.next = new ListNode(7);
        head1.next.next.next.next.next = new ListNode(8);
        head1.next.next.next.next.next.next = new ListNode(10);

        ListNode head2 = new ListNode(-10);
        head2.next = new ListNode(-3);
        head2.next.next = new ListNode(-0);
        head2.next.next.next = new ListNode(5);
        head2.next.next.next.next = new ListNode(9);
//        TreeNode treeNode = convertLinkToBST1(head1);
//        TreeNode treeNode1 = convertLinkToBST1(head2);
        TreeNode treeNode = convertLinkToBST2(head1);
        TreeNode treeNode1 = convertLinkToBST2(head2);
        TreeUtil.printTree(treeNode);
        TreeUtil.printTree(treeNode1);
    }
}
